package LeetCode;

/**
 * @author VX5
 * @Title: MJC
 * @ProjectName interview
 * @Description: TODO
 * @date ${DAT}22:33
 */
public class LeetCode79 {
    private boolean flag;
    public boolean exist(char[][] board, String word) {
        if(board == null || board.length == 0 || board[0].length == 0 ) {
            return false;
        }
        boolean result = false;
        for (int i = 0; i < board.length; i++){
            for (int j = 0; j < board[0].length; j++){
                result = searchWord(board,word,0,i,j);
                if (result){
                    return true;
                }
            }
        }
        return false;
    }

    // 从board[startx][staty]开始，寻找word[index...word,length
    public boolean searchWord(char[][] board,String word,int index,int startx,int starty){
        if (startx < 0 || starty < 0){
            return false;
        }
        if (startx > board.length - 1 || starty > board[0].length - 1 || board[startx][starty] == '/'){
            return false;
        }

        if (index == word.length() - 1){
            flag = board[startx][starty] == word.charAt(index);
            return flag;
        }
        boolean res = false;

        if (board[startx][starty] == word.charAt(index)){
            index++;
        }

        //当前字符匹配，进行下一轮 向四个方向寻找
        if (!flag) {
            char temp = board[startx][starty];
            board[startx][starty] = '/';
            res = searchWord(board, word, index, startx - 1, starty) ||
                    searchWord(board, word, index, startx, starty - 1) ||
                    searchWord(board, word, index, startx + 1, starty) ||
                    searchWord(board, word, index, startx, starty + 1);
            board[startx][starty] = temp;
        }else {
            return true;
        }

        return res;
    }

    public static void main(String[] args) {
        char[][] board = {
                {'A','B','C','E'},
                {'S','F','C','S'},
                {'A','D','E','E'}
        };
        String word = "SEE";
        System.out.println(new LeetCode79().exist(board, word));
    }
}
